The present invention relates generally to image compression, and, more particularly, to a novel method for compressing a set of images by partitioning the set of images into at least one representative image and at least one non-representative image, and then using the at least one representative image as a reference image to differentially or predictively code the at least one non-representative image, thereby exploiting the redundancy among images to significantly improve image compression efficiency. As used hereinthroughout, the term image(s) refers to still pictures as opposed to moving pictures. Also, in general, it will be appreciated by those having ordinary skill in the pertinent art that the image compression techniques disclosed herein can be used to compress the images contained in an image database for transmission, processing, editing, handling, or for any other purpose. In this connection, the utility of the present application is not limited to any particular application, and the present invention is not limited to any particular application.
Typically, when a set of images is compressed, each individual image is compressed schemes like the one specified by the JPEG standard utilize spatial correlation to represent an image with fewer bits in order to thereby achieve compression. However, no presently known image compression technique attempts to predictively code one image with respect to another image in order to exploit the redundancy among images, to thereby achieve a higher level of image compression. Although motion coding is commonly employed in compressing moving pictures by predictively coding some pictures with reference to other pictures in order to achieve a higher level of compression, an analogous technique has not been applied to image compression.
Based on the above, it can be appreciated that there presently exists a need in the art for an image compression technique that not only attempts to exploit the spatial correlation in a given image, but also the correlation between different images, in order to thereby achieve a significantly higher level of image compression. The present invention fulfills this need in the art by utilizing content-based similarity (used in search and retrieval of similar images in an image database) to efficiently compress a given set of images. The given set of images is first grouped into different clusters based on their color similarity. From each cluster, a set of representative images are chosen. These representative images are coded with either a lossless coding scheme or a lossy coding scheme with a very high fidelity. The other images present in a cluster are coded predictively using these representative images. (The terms coding and compression are used interchangeably hereinthroughout.)
The present invention, in its broadest aspect, encompasses a method for compressing a set of images or sub-images that includes the steps of designating at least one representative image or sub-image in the set of images or sub-images, all other images or sub-images within the set of images or sub-images being designated as non-representative images or sub-images; independently coding the representative image(s) or sub-image(s), and, predictively coding each of the non-representative images or sub-images using the representative image(s) or sub-image(s) as a reference image(s) or sub-image(s). The present invention further encompasses a method for compressing a set of images that includes the steps of grouping the images into at least two clusters based on image similarity according to at least one image similarity measure, identifying at least one representative image in each of the clusters, all other images within each of the clusters being identified as non-representative images, independently coding the representative image(s) from each of the clusters, e.g., using a lossy (e.g., JPEG) or lossless coding algorithm; and, predictively coding each of the non-representative images from each of the clusters using the representative image(s) from that cluster as a reference image(s). In a presently preferred embodiment, the image similarity measure comprises a color similarity measure. However, the image similarity measure can be any suitable image similarity measure or combination thereof, e.g., a color similarity measure, a texture similarity measure, a shape similarity measure, a geometrical similarity measure, and/or a content similarity measure.
The present invention also encompasses a method for compressing a set of images, that includes the steps of subdividing each image into a two or more partitions; grouping corresponding ones of the partitions having corresponding locations in their respective images into at least two clusters based on image similarity according to at least one similarity measure, to thereby produce a set of clusters for each set of corresponding ones of the partitions; identifying at least one representative image for each cluster of partitions, all other images within each of the clusters being identified as non-representative images; independently coding a reference partition in the representative image(s) for each of the clusters; and, predictively coding each of the partitions in the non-representative images for each of the clusters using the reference partition(s) in the representative image(s) for that cluster as a reference partition(s). In one embodiment, the method further includes the step of subdividing, for each cluster, each partition of each non-representative image into a plurality of smaller target blocks, and each partition of the representative image(s) into a plurality of smaller reference blocks having the same size as the target blocks, wherein the predictively coding step is carried out, for each cluster, by:
for each of the target blocks, comparing the pixels of that target block to the pixels of each of the same-sized reference blocks in the reference partition(s) according to a prescribed search metric, and producing an error metric value for each comparison made;
for each of the target blocks, determining whether the value of any of the error metric values produced is less than a prescribed maximum threshold value, and:
if so, identifying the one of the same-sized reference blocks that constitutes the best match for that target block, and,
if not, independently coding that target block.
In another embodiment, the predictively coding step is carried out by, for each cluster, coding a difference between each non-representative partition and the reference partition(s) for that cluster.
The present invention also encompasses a method for compressing a set of sub-images that includes the steps of designating at least one representative sub-image in the set of sub-images, all other sub-images within the set of sub-images being designated as non-representative sub-images; independently coding the representative sub-image(s); and, predictively coding each of the non-representative sub-images using the representative sub-image(s) as a reference sub-image(s).
The present invention also encompasses a method for compressing a set of images that includes the steps of subdividing each image into a two or more partitions; grouping the partitions into at least two clusters based on image similarity according to at least one similarity measure; identifying at least one representative partition for each cluster of partitions, all other partitions within each of the clusters being identified as non-representative partitions; independently coding the representative partition(s) for each of the clusters; and, predictively coding each of the non-representative partitions in each of the clusters using the representative partition(s) for that cluster as a reference partition(s). In one embodiment, the method further includes the step of subdividing, for each cluster, each non-representative partition into a plurality of smaller target blocks, and the reference partition(s) into a plurality of smaller reference blocks having the same size as the target blocks, wherein the predictively coding step is carried out, for each cluster, by:
for each of the target blocks, comparing the pixels of that target block to the pixels of each of the same-sized reference blocks in the reference partition(s) according to a prescribed search metric, and producing an error metric value for each comparison made;
for each of the target blocks, determining whether the value of any of the error metric values produced is less than a prescribed maximum threshold value, and:
if so, identifying the one of the same-sized reference blocks that constitutes the best match for that target block, and,
if not, independently coding that target block.
In another embodiment, the predictively coding step is carried out by, for each cluster, coding a difference between each non-representative partition and the reference partition(s) for that cluster.
In accordance with another optional aspect of the present invention, when a particular target image or partition has more than one reference image or partition in its cluster, then the one of the reference images or partitions that is the most similar, or at least most likely the most similar, e.g., the one of the reference images or partitions that shares the nearest common ancestor node in the cluster tree for that node, is selected as the reference image or partition for that particular target image or partition.
In a presently preferred embodiment, the method further includes the preliminary steps of partitioning each of the images into a plurality of color comparison blocks; computing a normalized histogram for each of the color comparison blocks of each image; and, using the computed normalized histograms in performing the grouping and identifying steps.
In an exemplary embodiment, each of the non-representative images or sub-images is coded with reference to a selected reference image or sub-image by partitioning the non-representative image or sub-image into a plurality of target blocks of pixels; for each of the target blocks, comparing the pixels of that target block to the pixels of each of the same-sized reference blocks in the reference image or sub-image according to a prescribed search metric, and producing an error metric value for each comparison made; and, for each of the target blocks, determining whether the value of any of the error metric values produced is less than a prescribed maximum threshold value, and:
if so, identifying the one of the same-sized reference blocks that constitutes the best match for that target block, and,
if not, independently coding that target block.
The coded data stream can also include coded data identifying the reference blocks of the reference images that constitute the best match for the respective target blocks of each of the non-representative images that are not independently coded, identifying which of the target blocks of each of the non-representative images are independently coded, and further, identifying which of the images of the set of images are reference images, and which are non-representative images. Alternatively, or additionally, the predictively coding step can include the sub-steps of, for each of the target blocks that are not independently coded, computing a difference between that target block and the reference block that constitutes its best match, to produce a residual value for each of the target blocks that are not independently coded, wherein coded data representative of the computed residual values can also be inserted into the coded data stream.
The present invention also includes a device that implements the methodologies of the present invention.